/*
 * @lc app=leetcode.cn id=1765 lang=typescript
 *
 * [1765] 地图中的最高点
 */

// @lc code=start
function highestPeak(isWater: number[][]): number[][] {
  const m = isWater.length;
  const n = isWater[0].length;
  // -1表示未安排高度的格子
  const ans: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(-1));
  const queue: number[][] = [];
  // 将所有的水域坐标放入队列
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (isWater[i][j] === 1) {
        ans[i][j] = 0;
        queue.push([i, j]);
      }
    }
  }
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  while (queue.length) {
    const [x, y] = queue.shift()!;
    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;
      if (nx < 0 || nx >= m) continue;
      if (ny < 0 || ny >= n) continue;
      if (ans[nx][ny] !== -1) continue;
      ans[nx][ny] = ans[x][y] + 1;
      queue.push([nx, ny]);
    }
  }

  return ans;
}
// @lc code=end
